import java.util.Scanner;
import java.util.Arrays;

public class MaxSubarraySum {

    /**
     * 使用Kadane算法找出最大子数组和
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int findMaxSubarraySum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // 对于当前元素，要么加入前面的子数组，要么重新开始
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            // 更新全局最大值
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

    /**
     * 修正的扩展方法：同时返回最大和以及对应的子数组
     */
    public static SubarrayResult findMaxSubarrayWithDetails(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new SubarrayResult(0, -1, -1);
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        int start = 0, end = 0;
        int tempStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (maxEndingHere < 0) {
                maxEndingHere = nums[i];
                tempStart = i;
            } else {
                maxEndingHere += nums[i];
            }

            if (maxEndingHere > maxSoFar) {
                maxSoFar = maxEndingHere;
                start = tempStart;
                end = i;
            }
        }

        return new SubarrayResult(maxSoFar, start, end);
    }

    // 辅助类，用于存储结果
    static class SubarrayResult {
        int maxSum;
        int startIndex;
        int endIndex;

        public SubarrayResult(int maxSum, int startIndex, int endIndex) {
            this.maxSum = maxSum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public int[] getSubarray(int[] nums) {
            if (startIndex == -1 || endIndex == -1) {
                return new int[0];
            }
            int[] result = new int[endIndex - startIndex + 1];
            System.arraycopy(nums, startIndex, result, 0, result.length);
            return result;
        }

        @Override
        public String toString() {
            return String.format("最大和: %d, 子数组区间: [%d, %d]", maxSum, startIndex, endIndex);
        }
    }

    /**
     * 从用户输入解析整数数组
     * 支持多种分隔符：空格、逗号、分号等
     */
    public static int[] parseInputArray(String input) {
        if (input == null || input.trim().isEmpty()) {
            return new int[0];
        }

        // 使用正则表达式分割字符串，支持多种分隔符
        String[] parts = input.split("[,\\s;]+");
        int[] result = new int[parts.length];

        for (int i = 0; i < parts.length; i++) {
            try {
                result[i] = Integer.parseInt(parts[i].trim());
            } catch (NumberFormatException e) {
                System.out.println("错误: '" + parts[i] + "' 不是有效的整数，将被忽略。");
                // 如果遇到无效输入，可以返回null或抛出异常
                // 这里我们简单地将无效输入设为0
                result[i] = 0;
            }
        }

        return result;
    }

    /**处理用户输入并计算结果*/
    public static void processUserInput() {
        Scanner scanner = new Scanner(System.in);

        System.out.println("=== 最大子数组和计算器 ===");
        System.out.println("请输入整数数组，数字之间用空格、逗号或分号分隔：");
        System.out.println("示例: 1 -2 3 5 -1 或 1,-2,3,5,-1");
        System.out.print("请输入数组: ");

        String input = scanner.nextLine();
        int[] array = parseInputArray(input);

        if (array.length == 0) {
            System.out.println("错误: 输入为空或格式不正确！");
            return;
        }

        System.out.println("解析后的数组: " + Arrays.toString(array));

        // 计算并显示结果
        int maxSum = findMaxSubarraySum(array);
        SubarrayResult detailedResult = findMaxSubarrayWithDetails(array);
        int[] maxSubarray = detailedResult.getSubarray(array);

        System.out.println("\n=== 计算结果 ===");
        System.out.println("最大子数组和: " + maxSum);
        System.out.println(detailedResult);
        System.out.println("最大和子数组: " + Arrays.toString(maxSubarray));

        // 验证结果
        System.out.println("\n=== 验证 ===");
        int subarraySum = 0;
        for (int num : maxSubarray) {
            subarraySum += num;
        }
        System.out.println("计算子数组和: " + subarraySum);
        System.out.println("算法结果: " + maxSum);
        System.out.println("验证结果: " + (subarraySum == maxSum ? "正确" : "错误"));

        scanner.close();
    }

    // 测试方法
    public static void main(String[] args) {
        // 如果提供了命令行参数，使用命令行参数
        if (args.length > 0) {
            System.out.println("使用命令行参数:");
            StringBuilder inputBuilder = new StringBuilder();
            for (String arg : args) {
                inputBuilder.append(arg).append(" ");
            }
            String input = inputBuilder.toString().trim();
            int[] array = parseInputArray(input);

            if (array.length > 0) {
                System.out.println("数组: " + Arrays.toString(array));
                int maxSum = findMaxSubarraySum(array);
                System.out.println("最大子数组和: " + maxSum);
            }
        } else {
            // 否则进入交互式模式
            processUserInput();
        }

        // 保留原有的测试用例
        System.out.println("\n=== 预定义测试用例 ===");
        int[][] testCases = {
                {2, -2, 3, 6, -1},      // 期望结果: 9
                {1, -2, 3, -8, 5, 5},   // 期望结果: 10
                {1, -2, 3, -2, 9, 1},   // 期望结果: 11
                {-2, -3, 4, -5, -2, 1, 5, -3}, // 期望结果: 6
        };

        for (int i = 0; i < testCases.length; i++) {
            int result = findMaxSubarraySum(testCases[i]);
            System.out.printf("测试数组%d %s: 最大子数组和 = %d%n",
                    i + 1, Arrays.toString(testCases[i]), result);
        }

        // 特别测试用户输入的数组
        System.out.println("\n=== 用户输入数组验证 ===");
        int[] userArray = {5, 6, 6, -5, 1, 15, 22, 1};
        SubarrayResult userResult = findMaxSubarrayWithDetails(userArray);
        int[] userSubarray = userResult.getSubarray(userArray);
        System.out.println("用户数组: " + Arrays.toString(userArray));
        System.out.println("最大子数组和: " + userResult.maxSum);
        System.out.println("最大和子数组: " + Arrays.toString(userSubarray));

        // 手动计算验证
        int manualSum = 0;
        for (int num : userSubarray) {
            manualSum += num;
        }
        System.out.println("手动计算子数组和: " + manualSum);
    }
}